#include <iostream>
using namespace std;

// 快速幂算法（递归实现）
long long fastPower(long long base, long long power, long long mod) {
    if (power == 0) return 1 % mod;
    long long half = fastPower(base, power / 2, mod);
    long long result = (half * half) % mod;
    if (power % 2 == 1) result = (result * base) % mod;
    return result;
}

// 快速幂算法（迭代实现）
long long fastPowerIterative(long long base, long long power, long long mod) {
    long long result = 1;
    base %= mod;
    while (power > 0) {
        if (power % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        power /= 2;
    }
    return result;
}

// 测试代码
int main() {
    long long base, power, mod;
    cin >> base >> power >> mod;

    cout << fastPower(base, power, mod) << endl;
    cout << fastPowerIterative(base, power, mod) << endl;
    while(1){}
    return 0;
}